package 中等.前缀和与差分;

/**
 * 给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。
 * 你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 
 * (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。
 * 请你返回使 s 平衡 的 最少 删除次数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced
 */
public class 使字符串平衡的最少删除次数_1653 {

    public static void main(String[] args) {

    }

    /**
     * 前缀和+枚举ab分割点
     */
    public int minimumDeletions(String s) {
        char[] chars = s.toCharArray();
        int[] suffixA = new int[s.length()];
        suffixA[s.length() - 1] = chars[s.length() - 1] == 'a' ? 1 : 0;

        for (int i = suffixA.length - 2; i >= 0; i--) {
            suffixA[i] = suffixA[i + 1];
            if (chars[i] == 'a') {
                suffixA[i]++;
            }
        }
        int preSumB = 0;
        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < s.length(); i++) {
            ans = Math.min(ans, preSumB + suffixA[i]);

            if (chars[i] == 'b') {
                preSumB++;
            }
        }
        ans = Math.min(ans, preSumB);
        return ans;
    }

}
